import copy
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        mapper={}
        lmapper={}
        for i in words:
            lmapper[i[0]]=1
            if i in mapper:
                mapper[i]+=1
            else:
                mapper[i]=1
        result=[]
        n=len(words[0])
        length=len(words)*len(words[0])
        for i in range(0,len(s)-length+1):
            if s[i] in lmapper:
                tmapper=copy.deepcopy(mapper)
                flag=True
                for j in range(len(words)):
                    if s[i+j*n:i+(j+1)*n] in tmapper:
                        if tmapper[s[i+j*n:i+(j+1)*n]]==1:
                            del tmapper[s[i+j*n:i+(j+1)*n]]
                        else:
                            tmapper[s[i+j*n:i+(j+1)*n]]-=1
                    else:
                        flag=False
                        break
                if flag:
                    result.append(i)
        return result

'''
执行用时：
1712 ms
, 在所有 Python3 提交中击败了
17.71%
的用户
内存消耗：
15.2 MB
, 在所有 Python3 提交中击败了
36.38%
的用户
'''

import copy
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        combs={}
        l=len(words)*len(words[0])
        visited=[0]*len(words)
        def dfs(c):
            nonlocal l
            if len(c)==l:
                combs[c]=1
            for i in range(len(words)):
                if visited[i]==0:
                    visited[i]=1
                    dfs(c+words[i])
                    visited[i]=0
        dfs("")
        result=[]
        for i in range(len(s)-l+1):
            if s[i:i+l] in combs:
                result.append(i)
        return result

'''
超时
'''